//https://leetcode.cn/problems/3sum/submissions/585056784/
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        int n = nums.size();
        vector<int> next(n, 1);
        sort(nums.begin(), nums.end());
        unordered_map<int, int> hash;
        int perv = nums[n - 1];
        for (int i = n - 2; i >= 0; --i)
        {
            if (nums[i] == perv) { next[i] = next[i + 1] + 1; }
            else { perv = nums[i]; }
        }
        for (int i = 0; i < n - 2;)
        {
            if (nums[i] > 0)break;
            int left = i + 1, right = n - 1; int tmp = -nums[i];
            while (left < right)
            {
                if (nums[left] + nums[right] < tmp)left++;
                else if (nums[left] + nums[right] > tmp)right--;
                else {
                    ret.push_back({ nums[left],nums[right],nums[i] });
                    left += next[left];
                    right -= next[right];
                }
            }
            i += next[i];
        }
        return ret;
    }
};